package com.javabasic.algorithm.leetcode;

import java.util.HashSet;

/**
 * @Author xiongmin
 * @Description
 * @Date 2021-04-11 16:47
 * @Version 1.0
 **/
public class UglyNumber {

    private HashSet<Integer> factorNums;
    private HashSet<Integer> targetFactorNums;

    public boolean isUgly(int n) {
        if (n < 0) {
            return false;
        }
        if (n == 1) {
            return true;
        }
        factorNums = new HashSet<>();
        targetFactorNums = new HashSet<>();
        targetFactorNums.add(2);
        targetFactorNums.add(3);
        targetFactorNums.add(5);
        eulerFun(n);
        int nums = factorNums.size();
        if(nums > 3) {
            return false;
        }
        boolean result = targetFactorNums.containsAll(factorNums) && (nums > 0);
        return result;
    }

    /**
     * 欧拉函数
     * 超时：2147483647
     * @param n
     * @return result  表示1-n与n互质的个数
     */
    public int eulerFun(int n) {
        int result = n;
        for (int i = 2; i*i <= n; i++) {
            if (n%i == 0) {
                result = result/i*(i-1);
                factorNums.add(i);
                if (factorNums.size() > 3) {
                    return 4;
                }
            }
            while (n%i == 0) {
                n /= i;
            }
        }
        if (n > 1) {
            result = result/n*(n-1);
            factorNums.add(n);
        }
        return result;
    }

    /**
     * P = 2^x*3^y*5^z
     * @param n
     * @return
     */
    public boolean isUgly2(int n) {
        if (n < 0) {
            return false;
        }
        while (n%5 == 0) {
            n /= 5;
        }
        while (n%3 == 0) {
            n /= 3;
        }
        while (n%2 == 0) {
//            n /= 2;
            n >>= 1;
        }
        return n == 1;
    }



}
